package main

func checkIsValid(s string) bool {
	stack := make([]byte, 0)
	for i := 0; i < len(s); i++ {
		if s[i] == ')' {
			if len(stack) > 0 {
				stack = stack[1:]
			} else {
				return false
			}
		} else {
			stack = append(stack, '(')
		}
	}

	if len(stack) == 0 {
		return true
	}

	return false
}

func dfsCreate(s string, i, n int, res *[]string) {
	if i == n {
		if checkIsValid(s) {
			*res = append(*res, s)
		}
		return
	}

	dfsCreate(s+"(", i+1, n, res)
	dfsCreate(s+")", i+1, n, res)
}

func generateParenthesis2(n int) []string {
	res := make([]string, 0)
	dfsCreate("", 0, n*2, &res)
	return res
}

func CreateStr(n int) []string {
	res := make([]string, 0)
	res = append(res, "(")
	res = append(res, ")")
	for i := 1; i < n; i++ {
		size := len(res)
		for j := 0; j < size; j++ {
			res = append(res, res[j]+"(")
			res = append(res, res[j]+")")
		}
	}

	return res[len(res)-8:]
}

func generateParenthesis(n int) []string {
	res := make([]string, 0)
	dfsCreate("", 0, n*2, &res)
	return res
}
